#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <queue>

using namespace std;

// 2163. 删除元素后和的最小差值
// https://leetcode.cn/problems/minimum-difference-in-sums-after-removal-of-elements/description/?envType=daily-question&envId=2025-07-18

class Solution
{
public:
    long long minimumDifference(vector<int> &nums)
    {
        long long n = nums.size() / 3;
        priority_queue<long long, vector<long long>, greater<long long>> maxQueue(nums.end() - n, nums.end());
        long long maxSum = accumulate(nums.end() - n, nums.end(), 0LL);
        // 后缀最大和
        vector<long long> maxBackSum(n + 1);
        long long index = n;
        maxBackSum[n] = maxSum;
        for (long long i = nums.size() - n - 1; i >= n; i--)
        {
            long long topNum = maxQueue.top();
            if (nums[i] > topNum)
            {
                maxSum -= topNum;
                maxSum += nums[i];
                maxQueue.pop();
                maxQueue.push(nums[i]);
            }
            maxBackSum[--index] = maxSum;
        }

        priority_queue<long long> minQueue(nums.begin(), nums.begin() + n);
        long long minSum = accumulate(nums.begin(), nums.begin() + n, 0LL);

        long long ans = minSum - maxBackSum[0];
        index = 0;
        for (long long i = n; i < nums.size() - n; i++)
        {
            long long topNum = minQueue.top();
            if (topNum > nums[i])
            {
                minSum -= topNum;
                minSum += nums[i];
                minQueue.pop();
                minQueue.push(nums[i]);
            }
            ans = min(ans, minSum - maxBackSum[++index]);
        }
        return ans;
    }
};

long long main()
{
    return 0;
}